#!/usr/bin/php
<?PHP

function arrayInit(array & $arr, int $max = 0,
                        bool $rand = TRUE, int $rand_max = 9999999)
{
    for ($i = 0, $m = $max == 0 ? sizeof($arr): $max; $i < $m; ++$i) {
        if ($rand)
            $arr[$i] = mt_rand(0, $rand_max);

        else {
            printf("请输入整型数(%d): ", $i);
            fscanf(STDIN, "%d", $arr[$i]);
        }
    }
}

function arrayOut(array & $arr, string $prompt = "")
{
    echo "$prompt";
    foreach ($arr as $val) {
        echo "$val ";
    }
    echo "\n";
}

//排序 -- 为了二分查找

// 冒泡排序  相邻两个数比较，第一个数比第二大数则交换
function bubble(array & $arr)
{
    $total = sizeof($arr);

    for ($i = 0, $l = $total - 1; $i < $l; $i++) {
        for ($j = 0, $k = $total - $i - 1; $j < $k; ++$j) {
            if ($arr[$j] > $arr[$j + 1]) {
                $arr[$j] ^= $arr[$j + 1];
                $arr[$j + 1] ^= $arr[$j];
                $arr[$j] ^= $arr[$j + 1];
            }
        }
    }
}
// 选择排序  将最小数查找到与第一个数交换
function select(array & $arr)
{
    $total = sizeof($arr);

    for ($i = 0, $l = $total - 1; $i < $l; ++$i) {
        for ($j = $i + 1, $m = $arr[$i], $index = $i; $j < $total; ++$j) {
            if ($m > $arr[$j]) {
                $m = $arr[$j];
                $index = $j;
            }
        }
        $arr[$index] = $arr[$i];
        $arr[$i] = $m;
    }
}

// 插入排序  已知左边数据为有序，将右边新数据元素从右向左查找合适位置插入
function insert(array & $arr)
{
    $total = sizeof($arr);

    /*
     * 3 5 1 4 9 2 6
     *     m = 5
     * 3 5 1 4 9 2 6
     *     m = 1
     * 1 3 5 4 9 2 6
     */

    for ($i = 1; $i < $total; ++$i) {
        $m = $arr[$i];
        for ($j = $i; $j > 0 && $m < $arr[$j - 1]; --$j)
        {
            $arr[$j] = $arr[$j - 1];
        }
        $arr[$j] = $m;
    }
}

// PHP内置排序方法为快速排序  空间换时间， 递归/栈

$a = array();
arrayInit($a, 10000, TRUE, 10000);
// arrayInit($a, 10, TRUE, 100);
// arrayOut($a, "init: ");
// bubble($a);
// select($a);
// insert($a);
sort($a);
// arrayOut($a, "sort: ");




